package com.zecan.kmp;

import org.junit.Test;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: lenovo
 * \* Date: 2021/10/11
 * \* Time: 22:05
 * \* Description:
 * \
 */
public class KMPAlgrothm {

    public static void main(String[] args) {
        String s = "BB ABCABABD";
        String t = "BAB";
        int kmp = KMP(s, t);
        System.out.println(kmp);

    }


    public static int KMP(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        char[] stoChar = s.toCharArray();
        char[] ttoChar = t.toCharArray();
        int[] next = getNext(t);
        int i = 0 ; // 指向文本串的索引
         int j = 0; // 指向模式串的索引
        while(i < sLen && j < tLen) {
            if(j == -1 || stoChar[i] == ttoChar[j]) {
                i++;
                j++;
            }else {
                j = next[j]; //如果不相等 那么就将j 回溯到最大公共子串的下标位置
            }
        }

        if(j >= tLen) {
            return i - j;
        }else {
            return -1;
        }
    }

    public static int[] getNext(String tt) {
        int tLen = tt.length();
        char[] ttChar = tt.toCharArray();
        int[] next = new int[tLen];
        int j = 0;
        int k = -1;
        next[j] = k;
        while(j < tLen - 1) {
            if(k == -1 || ttChar[j] == ttChar[k]) {
                j++;
                k++;
                next[j] = k;
                /*if (p[++j] == p[++k]) { // 当两个字符相等时要跳过  改进

              next[j] = next[k];

            } else {

              next[j] = k;

           }*/
            }else { // 因为此时前后缀没有相等的字符 所以 k 回溯到下一个位置进行比较
                k = next[k];
            }
        }
        return next;
    }
}
